#include <gtest/gtest.h>
#include "common.h"

using namespace ::std;

class Solution {
public:
    ListNode *detectCycle(ListNode *head);
};

// wrong implementation
// ListNode* Solution::detectCycle(ListNode *head) {
//     if(nullptr == head) return nullptr;
//     ListNode *slow = head, *fast = head, *ptr;
//     int firstMeetCount = 0, nodeInCycleCount = 0, pos = 0, meetCount = 0;
//     // cnt = nodeInCycleCount - pos
//     // 2 * pos + cnt = firstMeetCount
//     // pos + cnt = nodeInCycleCount
//     while(nullptr != fast) {
//         if(fast == slow) meetCount++;
//         if(3 == meetCount) break;
//         2 == meetCount ? nodeInCycleCount++ : firstMeetCount++;
//         slow = slow->next;
//         fast = fast->next != nullptr ? fast->next->next : nullptr;
//     }
//     cout << meetCount << " " << firstMeetCount << " " << nodeInCycleCount << endl;
//     pos = firstMeetCount - nodeInCycleCount;
//     cout << pos << endl;
//     return fast == nullptr ? nullptr : getCrossPoint(head, pos);
// }

ListNode* Solution::detectCycle(ListNode *head) {
    if(nullptr == head) return nullptr;
    ListNode *slow = head, *fast = head, *ptr = head;
    while(nullptr != fast) {
        slow = slow->next;
        fast = fast->next != nullptr ? fast->next->next : nullptr;
        if(slow == fast && fast != nullptr) {
            while(slow != ptr) {
                ptr = ptr->next;
                slow = slow->next;
            }
            break;
        }
    }
    return fast == nullptr ? nullptr : ptr;
}

class DetectCycleCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(DetectCycleCheck, testDetectCycle_1) {
    int pos = 5;
    vector<int> value = {3,2,0,-4,1,2,3,4,5,6,7,8,9};
    ListNode* head = makeCycleLinkedList(value, pos);
    EXPECT_TRUE(getCrossPoint(head, pos) == solution.detectCycle(head));
}

TEST_F(DetectCycleCheck, testDetectCycle_2) {
    int pos = 0;
    vector<int> value = {1,2};
    ListNode* head = makeCycleLinkedList(value, pos);
    EXPECT_TRUE(head == solution.detectCycle(head));
}

TEST_F(DetectCycleCheck, testDetectCycle_3) {
    int pos = -1;
    vector<int> value = {1};
    ListNode* head = makeCycleLinkedList(value, pos);
    EXPECT_TRUE(nullptr == solution.detectCycle(head));
}


int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}
